package everything.search;

import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import everything.Agent;
import everything.WorldMap;

public class SearchAgent extends Agent {

	protected Stack<String> _stack; // for reversing tree path



	protected int _xSentry;
	protected int _ySentry;
	protected String _dSentry;
	protected int T = 0;

	public SearchAgent(String name, String color, int x, int y, WorldMap map) {
		super(name, color, x, y, map);
		_type = "searchAgent";

	}

	public void initSentryLocation(int x, int y, String d) {
		//System.out.println("BLA");
		_xSentry = x;
		_ySentry = y;
		_dSentry = d;
	}

	protected static boolean isThreathened(int x,int y, int xSentry, int ySentry, String dSentry, WorldMap map){
		if ("SOUTH".equalsIgnoreCase(dSentry) || "NORTH".equalsIgnoreCase(dSentry)){
			if (y!=ySentry) {
				return false;
			} else {
				if (x > xSentry) {
					for (int i = xSentry ; i < x ; i++){
						if (map.isFireBlocked(i, ySentry)) return false;
					}
					return true;
				} else if (x < xSentry){
					for (int i = xSentry ; i > x ; i--){
						if (map.isFireBlocked(i, ySentry)) return false;
					}
					return true;
				} else return true;
			}
		} else if ("WEST".equalsIgnoreCase(dSentry) || "EAST".equalsIgnoreCase(dSentry)){	//direction is west/east
			if (x!=xSentry) {
				return false;
			} else {
				if (y > ySentry) {
					for (int i = ySentry ; i < y ; i++){
						if (map.isFireBlocked(xSentry, i)) return false;
					}
					return true;
				} else if (y < ySentry){
					for (int i = ySentry ; i > y ; i--){
						if (map.isFireBlocked(xSentry, i)) return false;
					}
					return true;
				} else return true;
			}
		} else return false;
	}

	@Override
	public boolean isKilling(int x, int y, WorldMap map) {
		return false;
	}

	@Override
	public void makeMove() {
		if (_stack == null){
			boolean[] tmp = new boolean[_map.getFlagList().size()];
			for (int i=0; i<tmp.length; i++){
				tmp[i] = true;
			}

			SearchAgentState state = new SearchAgentState(_xLocation, _yLocation, null, _xSentry, _ySentry, _dSentry, !isGhost(), tmp);
			ASearch Searchtmp = new ASearch(state, _map, this);
			ASearchNode node = Searchtmp.search(); // walking path
			T = Searchtmp.getT();  //number of expansions made

			_stack = new Stack<String>();
			while (node.getParent()!=null){
				_stack.push(node.getMove());
				node = node.getParent();
			}
		}
		try{
			move(_stack.pop());
		} catch(EmptyStackException e) {
			System.out.println("Reached destination - final score: " + _score);
		}
	}

	// path cost until now
	protected int g(ASearchNode n){
		boolean[] flags = n.getState().getFlags();
		int numTakenFlags = 0;
		for(int i=0; i<flags.length; i++){
			if (!flags[i]){
				numTakenFlags++;
			}
		}
		int ans = 0;
//		if (state.isTakingFlag()){
//			ans+=FLAG_SCORE;
//		}
		return ans + n.getDepth() - numTakenFlags*_map.getFlagValue();
	}

	// f = g + h - total cost
	public int f(ASearchNode n){
		return g(n) + h(n);
	}

	// huristic funciton value
	protected int h(ASearchNode n){

		//current heuristic function:
		// grade for the cell X is :
		//		the score of all the flags that the agent took + the cost of the minimum path from flag to flag minus those flags score, until all flags are taken or the bot is dead.
		//		that is - the agent tests for each flag whats the cost to get it , and adds the score of the flag minus the cost to get to that flag, then calculates the same for the next nearest flags
		//		the score is - the flags that the agent already has plus :
		//		A. the potential gain from going on the shortest path to get from flag to flag (by always going to the nearest flag first)
		//		B. or the cost to suicide without taking all of the flags (taking a series of flags by alwais going to the nearest flag -and then suicide)
		//
		//
		//		(gain = negative score, cost = positive score)
		//
		SearchAgentState state = n.getState();

		Queue<int[]> flags = processFlags(state.getX(), state.getY(), state.getXSentry(), state.getYSentry(), state.getDSentry(), state.getFlags(), _map);
		int minScoreForSuicide = _map.getHeight()*_map.getWidth()*(flags.size()+1);
		int weight = 0;
		if (!state.getHealth()) return weight; // returns 0 value for death (goal)
		int lastX = state.getX();
		int lastY = state.getY();
		while (!flags.isEmpty()){
			int[] flag = flags.poll();
			minScoreForSuicide = Math.min(minScoreForSuicide, weight + hSuicide(lastX, lastY, state.getXSentry(), state.getYSentry(), state.getDSentry(), state.getXSentry(), state.getYSentry(), state.getHealth(), _map));

			weight = weight + countMoves(lastX, lastY, state.getXSentry(), state.getYSentry(), state.getDSentry(), flag[0], flag[1], state.getHealth(), _map) - _map.getFlagValue();
			lastX = flag[0];
			lastY = flag[1];
		}
		return Math.min(weight, minScoreForSuicide);
	}

	// returns a list of the flags, sorted by distance (from previous location)
	public static Queue<int[]> processFlags(int startXPosition, int startYPosition, int xSentry, int ySentry, String dSentry, boolean[] flagState, WorldMap map){
		List<int[]> flagsCopy = new LinkedList<int[]>();

		List<int[]> tmpFlags = map.getFlagList();
		for (int i =0 ; i<tmpFlags.size() ; i++){
			if (flagState[i]){
				flagsCopy.add(tmpFlags.get(i));
			}
		}
		Queue<int[]> ans  = new LinkedList<int[]>();
		int xPosition = startXPosition;
		int yPosition = startYPosition;


		//System.out.println("Flag setup: [" +startXPosition + "," + startYPosition + "]");
		while(!flagsCopy.isEmpty()){
			int[] closestFlag = flagsCopy.get(0);
			int minDist = SearchAgent.countMoves(xPosition, yPosition, xSentry, ySentry, dSentry, closestFlag[0], closestFlag[1], true, map);
			for (int[] flag : flagsCopy) {
				int dist = SearchAgent.countMoves(xPosition, yPosition, xSentry, ySentry, dSentry, flag[0], flag[1], true, map);
				if (dist < minDist){
					minDist = dist;
					closestFlag = flag;
				}
			}
			//System.out.print("["+closestFlag[0]+","+closestFlag[1]+"] - "+minDist+", ");
			ans.add(closestFlag);
			flagsCopy.remove(closestFlag);
			xPosition = closestFlag[0];
			yPosition = closestFlag[1];
		}


		return ans;


	}


	public static int countMoves(int x, int y, int xSentry, int ySentry, String dSentry, int destX, int destY, boolean health, WorldMap map){
		int height = map.getHeight();
		int width = map.getWidth();
		if (destX==x && destY==y) return 0;

		// Initializations
		int[][] board_prev = new int[height][];
		int[][] board_dist = new int[height][];
		int maxlength = height*width;
		for (int i=0 ; i<board_prev.length; i++){
			board_prev[i] = new int[width];
			board_dist[i] = new int[width];
			for(int j=0; j<board_prev[i].length; j++){
				board_prev[i][j] = 0;			// Previous node in optimal path from source
				board_dist[i][j] = maxlength;	// Unknown distance function from source to v
			}
		}
		board_dist[x][y] = 0;					// Distance from source to source
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(new Integer(x*width+y+1));
		while (!Q.isEmpty() && board_prev[destX][destY]==0){
			int cell = Q.poll().intValue();
			int tmpX = cell / width;
			int tmpY = cell % width - 1;

			if (!(map.brickStatus(tmpX+1, tmpY) == WorldMap.WALL) && board_prev[tmpX+1][tmpY]==0 && !isThreathened(tmpX+1, tmpY, xSentry, ySentry, dSentry, map)){
				Q.add(new Integer((tmpX+1)*width+(tmpY)+1));
				board_prev[tmpX+1][tmpY] = cell;
				board_dist[tmpX+1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX, tmpY+1) == WorldMap.WALL) && board_prev[tmpX][tmpY+1]==0 && !isThreathened(tmpX, tmpY+1, xSentry, ySentry, dSentry, map)){
				Q.add(new Integer((tmpX)*width+(tmpY+1)+1));
				board_prev[tmpX][tmpY+1] = cell;
				board_dist[tmpX][tmpY+1] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX-1, tmpY) == WorldMap.WALL) && board_prev[tmpX-1][tmpY]==0 && !isThreathened(tmpX-1, tmpY, xSentry, ySentry, dSentry, map)){
				Q.add(new Integer((tmpX-1)*width+(tmpY)+1));
				board_prev[tmpX-1][tmpY] = cell;
				board_dist[tmpX-1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX, tmpY-1) == WorldMap.WALL) && board_prev[tmpX][tmpY-1]==0 && !isThreathened(tmpX, tmpY-1, xSentry, ySentry, dSentry, map)){
				Q.add(new Integer((tmpX)*width+(tmpY-1)+1));
				board_prev[tmpX][tmpY-1] = cell;
				board_dist[tmpX][tmpY-1] = board_dist[tmpX][tmpY]+1;
			}
		}
//				System.out.println("BOARD_PREV");
//				for (int i=0; i<board_prev.length; i++){
//				for (int j=0 ; j<board_prev[i].length; j++)
//				System.out.printf("%1$4d,",board_prev[i][j]);
//				System.out.println();
//				}
//				System.out.println("BOARD_DIST");
//				for (int i=0; i<board_prev.length; i++){
//				for (int j=0 ; j<board_prev[i].length; j++)
//				System.out.printf("%1$4d,",board_dist[i][j]);
//				System.out.println();
//				}
		if (board_prev[destX][destY]==0 || !health){
			return maxlength;
		} else {
			return board_dist[destX][destY];
		}
		//		Q := the set of all nodes in Graph    // All nodes in the graph are unoptimized - thus are in Q
		//		while Q is not empty:                 // The main loop
		//		u := node in Q with smallest dist[]
		//		remove u from Q
		//		for each neighbor v of u:         // where v has not yet been removed from Q.
		//		alt := dist[u] + dist_between(u, v)       // be careful in 1st step - dist[u] is infinity yet
		//		if alt < dist[v]              // Relax (u,v)
		//		dist[v] := alt
		//		previous[v] := u
		//		return previous[]
	}



	//calculates the minimum distance for suicide
	private static int hSuicide(int x, int y, int xSentry, int ySentry, String dSentry, int destX, int destY, boolean health, WorldMap map){
		int height = map.getHeight();
		int width = map.getWidth();
		if (destX==x && destY==y) return 0;

		// Initializations
		int[][] board_prev = new int[height][];
		int[][] board_dist = new int[height][];
		int maxlength = height*width;
		for (int i=0 ; i<board_prev.length; i++){
			board_prev[i] = new int[width];
			board_dist[i] = new int[width];
			for(int j=0; j<board_prev[i].length; j++){
				board_prev[i][j] = 0;			// Previous node in optimal path from source
				board_dist[i][j] = maxlength;	// Unknown distance function from source to v
			}
		}
		board_dist[x][y] = 0;					// Distance from source to source
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(new Integer(x*width+y+1));
		while (!Q.isEmpty() && board_prev[destX][destY]==0){
			int cell = Q.poll().intValue();
			int tmpX = cell / width;
			int tmpY = cell % width - 1;

			if (!map.isMovementBlocked(tmpX+1, tmpY) && board_prev[tmpX+1][tmpY]==0){
				if (isThreathened(tmpX+1, tmpY, xSentry, ySentry, dSentry, map)){
					board_prev[destX][destY] = 1;
					board_dist[destX][destY] = board_dist[tmpX][tmpY]+1;
				}
				Q.add(new Integer((tmpX+1)*width+(tmpY)+1));
				board_prev[tmpX+1][tmpY] = cell;
				board_dist[tmpX+1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!map.isMovementBlocked(tmpX, tmpY+1) && board_prev[tmpX][tmpY+1]==0){
				if (isThreathened(tmpX, tmpY+1, xSentry, ySentry, dSentry, map)){
					board_prev[destX][destY] = 1;
					board_dist[destX][destY] = board_dist[tmpX][tmpY]+1;
				}
				Q.add(new Integer((tmpX)*width+(tmpY+1)+1));
				board_prev[tmpX][tmpY+1] = cell;
				board_dist[tmpX][tmpY+1] = board_dist[tmpX][tmpY]+1;
			}
			if (!map.isMovementBlocked(tmpX-1, tmpY) && board_prev[tmpX-1][tmpY]==0){
				if (isThreathened(tmpX-1, tmpY, xSentry, ySentry, dSentry, map)){
					board_prev[destX][destY] = 1;
					board_dist[destX][destY] = board_dist[tmpX][tmpY]+1;
				}
				Q.add(new Integer((tmpX-1)*width+(tmpY)+1));
				board_prev[tmpX-1][tmpY] = cell;
				board_dist[tmpX-1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!map.isMovementBlocked(tmpX, tmpY-1) && board_prev[tmpX][tmpY-1]==0){
				if (isThreathened(tmpX, tmpY-1, xSentry, ySentry, dSentry, map)){
					board_prev[destX][destY] = 1;
					board_dist[destX][destY] = board_dist[tmpX][tmpY]+1;
				}
				Q.add(new Integer((tmpX)*width+(tmpY-1)+1));
				board_prev[tmpX][tmpY-1] = cell;
				board_dist[tmpX][tmpY-1] = board_dist[tmpX][tmpY]+1;
			}
		}
		if (board_prev[destX][destY]==0 || !health){
			return maxlength;
		} else {
			return board_dist[destX][destY];
		}
	}

	public int getT() {
		return T;
	}



	/*
	public static void main(String[] args) {

		new Thread(new Runnable(){
			public void run(){
				try {
					Mymain.main(new String[]{"Mymain"});
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}).start();

		WorldMap m;
		SearchAgent e;
		Automaton a;
		String line = "1";
		try{
			System.out.println("Enter test number");
			line  = new BufferedReader(new InputStreamReader(System.in)).readLine();
		}catch (Exception e1) {}
		if ("1".equals(line)){
			//test 1: agent has to move right and down to avoid the sentry
			m = new WorldMap("board5.txt");
			e = new SearchAgent("TEST","Blue",1,2,m, 2, 1, "NORTH");
			a = new Automaton("YOSI","Red",2,1,m,"NORTH");
		} else if("2".equals(line)){
			//test 2: agent has to move right/up(=stay in place) and down to avoid the sentry
			m = new WorldMap("board5.txt");
			e = new SearchAgent("TEST","Blue",1,3,m, 2, 1, "NORTH");
			a = new Automaton("YOSI","Red",2,1,m,"NORTH");
		} else if("3".equals(line)){
			//test 3: agent has to enter the ice on the right time
			m = new WorldMap("board6.txt");
			e = new SearchAgent("TEST","Blue",1,3,m, 4, 1, "NORTH");
			a = new Automaton("YOSI","Red",4,1,m,"NORTH");
		} else if("4".equals(line)){
			//test 4: other version of test 3
			m = new WorldMap("board9.txt");
			e = new SearchAgent("TEST","Blue",1,3,m, 4, 1, "NORTH");
			a = new Automaton("YOSI","Red",4,1,m,"NORTH");
		} else if("5".equals(line)){
			//test 4: other version of test 3
			m = new WorldMap("board7.txt");
			e = new SearchAgent("TEST","Blue",1,3,m, 4, 1, "NORTH");
			a = new Automaton("YOSI","Red",4,1,m,"NORTH");
		} else if("6".equals(line)){
			//test 5: big board, lots of flags
			m = new WorldMap("board8.txt");
			e = new SearchAgent("TEST","Blue",1,1,m, 8, 17, "NORTH");
			a = new Automaton("YOSI","Red",8,17,m,"NORTH");
		} else if("7".equals(line)){
			//test 5: big board, lots of flags
			m = new WorldMap("board10.txt");
			e = new SearchAgent("TEST","Blue",5,17,m, 1, 1, "WEST");
			a = new Automaton("YOSI","Red",1,1,m,"WEST");

		} else {
			m = null;
			e = null;
			a = null;
			System.out.println("INVALID TEST");
			System.exit(-1);
		}

		m.addAgent(e);
		m.addAgent(a);
		m.showScore();
		while(true){
			try {
				new BufferedReader(new InputStreamReader(System.in)).readLine();
				e.makeMove();
				new BufferedReader(new InputStreamReader(System.in)).readLine();
				a.makeMove();
			} catch (IOException e1) {
				e1.printStackTrace();
			}
		}
		//		System.out.println(a + "," + e.h(new SearchAgentState(1,1,null,2,11,"NORTH", true), 5, 15));
	}
*/
}

